#include "Builder_Backtracking.h"
#include "Log.h"

Builder_Backtracking::Builder_Backtracking(Verifier *verifier,
                                           Splitter *splitter) {
  this->splitter = splitter;
  this->verifier = verifier;
}

void Builder_Backtracking::build(Cluster& main_cluster) {
    LOG_ENTER(TREE, "Builder_Backtracking::build");

    Cluster *L,*R;

    //
    // Make an initial split, and seed the stack.
    //
    splitter->split(&main_cluster, L, R);

    tree.set_root(root);
    tree.set_children(root, L, R);

    tree.push_clusters(L, R);

    while (!pending_clusters.empty()) {
        //
        // At least tree clusters on stack.  Pop them.
        //
        tree.pop_clusters(L, R);

        vector<Tree_Of_Clusters *> *subtrees = verifier.verify(L, R);

        tree.replace_subtree(L, subtrees[0]);
        tree.replace_subtree(R, subtrees[1]);

        tree.push_tree_nodes(subtrees[0], pending_clusters);
        tree.push_tree_nodes(subtrees[1], pending_clusters);
    }
    else {
        //
        // split was OK.  Do nothing to tree.  L and R were made
        // children of S by push_clusters()
        //
        L->extend_labels(0);
        R->extend_labels(1);
    }

    LOG_EXIT();
}
